package leetcode_1100;

import java.util.PriorityQueue;

import helpclass.TreeNode;

public class RecoverATreeFromPreorderTraversal_1028 {
	public static void main(String[] args) {
		RecoverATreeFromPreorderTraversal_1028 test = new RecoverATreeFromPreorderTraversal_1028();
		System.out.println(test.recoverFromPreorder("10-7--8"));
	}
	
	class Help{
		TreeNode root;
		int level;
		public Help(TreeNode root,int level) {
			this.root = root;
			this.level = level;
		}
	}
	public TreeNode recoverFromPreorder(String S) {
		char []chars = S.toCharArray();
        int i =0;
        while(i<S.length() && chars[i] != '-') ++i;
        TreeNode root = new TreeNode(Integer.parseInt(S.substring(0,i)));
        PriorityQueue<Help> queue=  new PriorityQueue<Help>((o1,o2)->o2.level-o1.level);
        queue.offer(new Help(root,0));
        for(;i<S.length();++i) {
        	int run =i;
        	while(chars[run]=='-') ++run;
        	int level = run-i;
        	i = run;
        	while(run+1 != S.length() && chars[run+1] != '-') {
        		++run;
        	}
        	int val = Integer.parseInt(S.substring(i,run+1));
            i = run;
        	TreeNode now =new TreeNode(val);
        	Help help = new Help(now,level);
        	while(!queue.isEmpty() && queue.peek().level >= level) queue.poll();
        	if(queue.peek().root.left == null) queue.peek().root.left = now;
        	else queue.peek().root.right = now;
        	queue.offer(help);
        }
        return root;
    }
}
